/*
 * =====================================================================================
 *
 *       Filename:  qsort.cpp
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  12/15/2010 11:20:57 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Ken Chen (Ken), chen_kenz@emc.com
 *        Company:  EMC
 *
 * =====================================================================================
 */

#include <vector> 
#include <iterator>
#include <algorithm>
#include <iostream>

using namespace std;

int Partition(int intVec[], int low, int high)
{
  intVec[0] = intVec[low];
  int privot = intVec[low];
  
  while(low<high)
  {
    while((low<high)&&(intVec[high]>=privot)) high--;
    intVec[low] = intVec[high];
    while((low<high)&&(intVec[low]<=privot)) low++;
    intVec[high] = intVec[low];
  }
  intVec[low] = intVec[0];
  
  return low;
}

void QSort(int intVec[], int low, int high)
{
  if(low<high )
  {
    int mid = Partition(intVec, low, high);
    QSort(intVec, low, mid-1);
    QSort(intVec, mid+1, high);
  }
}

/*int array begins with 1, position 0 is reserved*/
void QuickSort( int intVec[], int size )
{
  QSort( intVec, 1, size );
}


int main( int argc, char* argv[] )
{
  int arr[] = { 0, 34, 12 , 4 ,35, 6, 8, 1, 1243 };
  vector<int> intVec( arr, arr+sizeof(arr)/sizeof(arr[0]) );
  QuickSort( arr, sizeof(arr)/sizeof(arr[0]) - 1 );

  copy( arr+1, arr+sizeof(arr)/sizeof(arr[0]), ostream_iterator<int>( cout, " ") );
}
